Search for: All records

Word-representable graphs were originally introduced by Kitaev and Pyatkin, motivated by work of Kitaev and Seif in algebra. Since their introduction, however, there has been a great deal of work in understanding their graph theoretical properties. In this paper, we introduce tools from partially ordered sets, Ramsey theory as well as probabilistic methods to study them. Through these, we settle a number of open problems in the field, regarding both the existence and length of word-representations for various classes of graphs. 

Abstract Let $$\gamma(G)$$ and $${\gamma _ \circ }(G)$$ denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G is an n -vertex graph of minimum degree at least d , then $$\begin{equation}\gamma(G) \leq \frac{n}{d}(\log d + 1).\end{equation}$$ In this paper the main result is that if G is any n -vertex d -regular graph of girth at least five, then $$\begin{equation}\gamma_(G) \leq \frac{n}{d}(\log d + c)\end{equation}$$ for some constant c independent of d . This result is sharp in the sense that as $$d \rightarrow \infty$$ , almost all d -regular n -vertex graphs G of girth at least five have $$\begin{equation}\gamma_(G) \sim \frac{n}{d}\log d.\end{equation}$$ Furthermore, if G is a disjoint union of $${n}/{(2d)}$$ complete bipartite graphs $$K_{d,d}$$ , then $${\gamma_\circ}(G) = \frac{n}{2}$$ . We also prove that there are n -vertex graphs G of minimum degree d and whose maximum degree grows not much faster than d log d such that $${\gamma_\circ}(G) \sim {n}/{2}$$ as $$d \rightarrow \infty$$ . Therefore both the girth and regularity conditions are required for the main result. 

Energy decomposition analysis (EDA) based on absolutely localized molecular orbitals (ALMOs) decomposes the interaction energy between molecules into physically interpretable components like geometry distortion, frozen interactions, polarization, and charge transfer (CT, also sometimes called charge delocalization) interactions. In this work, a numerically exact scheme to decompose the CT interaction energy into pairwise additive terms is introduced for the ALMO-EDA using density functional theory. Unlike perturbative pairwise charge-decomposition analysis, the new approach does not break down for strongly interacting systems, or show significant exchange–correlation functional dependence in the decomposed energy components. Both the energy lowering and the charge flow associated with CT can be decomposed. Complementary occupied–virtual orbital pairs (COVPs) that capture the dominant donor and acceptor CT orbitals are obtained for the new decomposition. It is applied to systems with different types of interactions including DNA base-pairs, borane-ammonia adducts, and transition metal hexacarbonyls. While consistent with most existing understanding of the nature of CT in these systems, the results also reveal some new insights into the origin of trends in donor–acceptor interactions. 

Quantum chemistry in the form of density functional theory (DFT) calculations is a powerful numerical experiment for predicting intermolecular interaction energies. However, no chemical insight is gained in this way beyond predictions of observables. Energy decomposition analysis (EDA) can quantitatively bridge this gap by providing values for the chemical drivers of the interactions, such as permanent electrostatics, Pauli repulsion, dispersion, and charge transfer. These energetic contributions are identified by performing DFT calculations with constraints that disable components of the interaction. This review describes the second-generation version of the absolutely localized molecular orbital EDA (ALMO-EDA-II). The effects of different physical contributions on changes in observables such as structure and vibrational frequencies upon complex formation are characterized via the adiabatic EDA. Example applications include red- versus blue-shifting hydrogen bonds; the bonding and frequency shifts of CO, N 2 , and BF bound to a [Ru(II)(NH 3 ) 5 ] 2 + moiety; and the nature of the strongly bound complexes between pyridine and the benzene and naphthalene radical cations. Additionally, the use of ALMO-EDA-II to benchmark and guide the development of advanced force fields for molecular simulation is illustrated with the recent, very promising, MB-UCB potential. 

Intermolecular interactions between radicals and closed-shell molecules are ubiquitous in chemical processes, ranging from the benchtop to the atmosphere and extraterrestrial space. While energy decomposition analysis (EDA) schemes for closed-shell molecules can be generalized for studying radical–molecule interactions, they face challenges arising from the unique characteristics of the electronic structure of open-shell species. In this work, we introduce additional steps that are necessary for the proper treatment of radical–molecule interactions to our previously developed unrestricted Absolutely Localized Molecular Orbital (uALMO)-EDA based on density functional theory calculations. A “polarize-then-depolarize” (PtD) scheme is used to remove arbitrariness in the definition of the frozen wavefunction, rendering the ALMO-EDA results independent of the orientation of the unpaired electron obtained from isolated fragment calculations. The contribution of radical rehybridization to polarization energies is evaluated. It is also valuable to monitor the wavefunction stability of each intermediate state, as well as their associated spin density profiles, to ensure the EDA results correspond to a desired electronic state. These radical extensions are incorporated into the “vertical” and “adiabatic” variants of uALMO-EDA for studies of energy changes and property shifts upon complexation. The EDA is validated on two model complexes, H 2 O⋯˙F and FH⋯˙OH. It is then applied to several chemically interesting radical–molecule complexes, including the sandwiched and T-shaped benzene dimer radical cation, complexes of pyridine with benzene and naphthalene radical cations, binary and ternary complexes of the hydroxyl radical with water (˙OH(H 2 O) and ˙OH(H 2 O) 2 ), and the pre-reactive complexes and transition states in the ˙OH + HCHO and ˙OH + CH 3 CHO reactions. These examples suggest that this second generation uALMO-EDA is a useful tool for furthering one's understanding of both energetic and property changes associated with radical–molecule interactions.